COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input lisp[206,tex]  % TEX file for Homework Set 5, Spring 1979
C00003 00003	\HeadA⊂Problem Set $\#$5 - Due May 8, 1979⊃
C00012 00004	\QUEST 2\ (Pattern Matching).
C00017 00005	\QUEST 3\ (Optional).
C00018 00006	\QUEST 4\ (Self-Generation).
C00020 00007	\QUEST 6\ (Auxilary Functions).
C00023 00008	\par\vfill\eject
C00024 ENDMK
C⊗;
\input lisp[206,tex]  % TEX file for Homework Set 5, Spring 1979
\def\underspace{$\underline {\hbox { }}$}

% This is hw set RDG wrote, handed out 1-May, due 8-May
\HeadA⊂Problem Set $\#$5 - Due May 8, 1979⊃

\QUEST 1\ (Diagnosing, Revisited).
A more complex data base for diagnosing patients has been created.
Each sympton associated with a disease will be in the form of a
\LISPE CONS|ed pair, of \LISPE (\cons ⊂symp-fn . symp-dis-require⊃)|.
The function, \LISPE symp-fn|,
expects a single argument: the patient in question. 
It then performs the appropriate interrogation
(which will be described in  a moment),
and returns some numeric value.

Associated with each patient, P, for every disease, d, 
is a number $\Phi↓{P,d} \in [0,1]$
which describes the likelihood P has this d.
Initially, this $\Phi↓{P,d}$ is set to $1$, indicating we have
no {\sl a priori} reason to believe P immune to this d.
During the diagnosis process,
its value will be updated to reflect newly determined information.

The other half of the symptom's \LISPE CONS|ed pair,
\LISPE symp-dis-require|,
encodes what to do with $\Phi↓{P,d}$'s value, based on
what this sympton's \LISPE symp-fn| returned for this patient.
When \LISPE symp-dis-require| is 
``\LISPI Must-Be|'', this symptom must be present. 
$\Phi↓{P,d}$ will therefore be reset to the product of its
current value, and the number returned by \LISPE symp-fn|.
If this returned value is $0$,
$\Phi↓{P,d}$ will become $0$,
which, we will see, indicates that P definitely does not have disease d.

When  \LISPE symp-dis-require| is ``\LISPI Must-Not-Be|'',
it is the probably that the P does NOT have the d which is
multiplied by the result: hence
$1- \Phi↓{P,d} \← 
{\hbox {\LISPE \funct symp-fn[ P ]|}} \times (1- \Phi↓{P,d})$.

Associated with each patient will be a set of attributes, specifying her
current condition.
These are placed on the property list of that patient.
Some subset of these are to be examined by each \LISPE symp-fn|.
To illustrate, suppose the patient \LISPI RDG| will have the properties
\LISPI Takes-LISP|, \LISPI Judgment| and  \LISPI Temperature|,
with respective values of ``$+$'', ``$-$'' and ``$101.3$''.
What had been the atom 
\LISPI Takes-LISP| in the data set used in last two assignments
will now be the function:

{\eightpoint
{\halign{{\qquad\lft{\LISPI #|}}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr
(DEFUN ⊗\nulsize{Takes-LISP (PATIENT)}\cr
⊗\nulsize{((LAMBDA (IN-CLASS)}\cr
⊗\ (COND ⊗((EQ IN-CLASS '$+$) ⊗1.0)\cr
⊗⊗((EQ IN-CLASS '$-$) ⊗0.0)\cr
⊗⊗(T ⊗0.5))))   ; just in case\cr
⊗\nulsize{\ (GET PATIENT 'Takes-Lisp))}\cr
}}}

A very similar \LISPI Has-Judgment| function can be composed:

{\eightpoint
{\halign{{\qquad\lft{\LISPI #|}}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr
(DEFUN ⊗\nulsize{Has-Judgment (PATIENT)}\cr
⊗\nulsize{((LAMBDA (COMPETENT)}\cr
⊗\ (COND ⊗((EQ COMPETENT '$++$) ⊗1.0)\cr
⊗⊗((EQ COMPETENT '$+$) ⊗0.66)\cr
⊗⊗((EQ COMPETENT '$-$) ⊗0.33)\cr
⊗⊗((EQ COMPETENT '{$-$}{$-$}) ⊗0.0)\cr
⊗⊗(T ⊗0.5))))   ; just in case\cr
⊗\nulsize{\ (GET PATIENT 'Judgment))}\cr
}}}

The formerly-used \LISPI High-Temperature| atom is now the more complex:

{\eightpoint % \vcenter
{\halign{{\qquad\lft{\LISPI #|}}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr
(DEFUN ⊗\nulsize{High-Temperature (PATIENT)}\cr
⊗\nulsize{((LAMBDA (TEMP)}\cr
⊗\ (COND ⊗((NULL TEMP) ⊗1.0)  {\rm; assume the worst}\cr
⊗⊗((> TEMP 102.0) ⊗1.0)\cr
⊗⊗((> TEMP 100.0) ⊗0.8)\cr
⊗⊗((> TEMP 98.6) ⊗0.6)\cr
⊗⊗(T ⊗0.0)))\cr
⊗\nulsize{\ (GET PATIENT 'Temperature))).}\cr
}}}

Let us now image the disease \LISPI Raving-Mad| has the requirements

{\eightpoint
\disptext {\LISPI 
( (\cons ⊂Takes-LISP . Must-Be⊃) 
(\cons ⊂High-Temperature . Must-Be⊃)
(\cons ⊂Has-Judgment . Must-Not-Be⊃) ),|}}

[i.e. this list is on \LISPI Raving-Mad|'s property list for \LISPI SYMPTOM|,]
and ask, does \LISPI RDG| has this ailment?
To find out, we have to run some tests:
Initially $\Phi↓{RDG,R-V} = 1.0$.
The value of \LISPI \funct Takes-LISP[ RDG ]| is $1.0$. As this is a 
\LISPI MUST-BE| condition, 
$\Phi↓{RDG,R-V} \← 1.0 \times \Phi↓{RDG,R-V}$ or $1.0$.
Next the value of \LISPI \funct High-Temperature[ RDG ]| is queried.
This yields $0.8$, and the resulting 
$\Phi↓{RDG,R-V}$ is $0.8 \times 1.0 = 0.8$.
The final test is 
\LISPI \funct Has-Judgment[ RDG ]|, which returns $0.33$.
As this is a \LISPI Must-Not-Be|,
$\Phi↓{RDG,R-V} \← 
1.0 - 0.33 \times (1.0 -0.8)$, or $0.934$.
We might then say that \LISPI RDG| is \LISPI Raving-Mad| with probability $0.934$.

As a final step in the diagnosis, we could apply a set of threshold levels to
govern what we print out. That is, we will state patient P DEFINITELY has disease
d when the final value of  $\Phi↓{P,d}$ exceeds $0.90$, that he PROBABLY has d
if $\Phi↓{P,d}$ is between $0.60$ and $0.90$,
that he MIGHT have d if between $0.40$ and $0.60$,
PROBABLY-NOT if $0.10 < \Phi↓{P,d} ≤ 0.40$,
and DEFINITELY-NOT if under $0.10$.
In this example, we would conclude \LISPI RDG| is DEFINITELY \LISPI Raving-Mad|.
Notice if only the first two tests were admininstered, we could only assume 
he is PROBABLY \LISPI Raving-Mad|.

The assignment is to read in the data set in HW5.LSP, 
(same ``CS206'' account as usual,) and return,
for each patient and each disease, the computed chance
(i.e. one of $\{$DEFINITELY PROBABLY MIGHT PROBABLY-NOT DEFINITELY-NOT$\}$)
that he has that malady.
To aid the unfortunate grader, please print these in some readable format
(e.g. in regular columns).
\NOTE The order in which these tests are applied WILL make a difference.
It should be done in the obvious left-to-right order.\eton
\HINT You may need only modify the function \LISPI Probably-Has|.\tnih
\QUEST 2\ (Pattern Matching).

\HeadC ⊂Part 1⊃
Write a function, \LISPI Code[ pattern ]|,
which instantiates its argument, \LISPE pattern|.
It should replace every atom (within the S-expression of this argument,)
of the form ``\LISPI ?x|'' (i.e. an atom whose first letter is ``?'',)
with the value of this atom.
Every atom beginning with the symbol ``*'' should be replaced
with the contents of the list of that variable's value.
For example, when  \LISPI ?name| is bound to the value \LISPI RUSS|,
the function \LISPE \funct CODE[ (MY NAME IS ?name) ]| will return
\LISPI (MY NAME IS RUSS)|. 
After \LISPI (setq *full-name '(DOUGLAS LENAT))|, the value of
\LISPI \funct CODE[ (HIS NAME IS *full-name) ]| is 
\LISPI (HIS NAME IS DOUG LENAT)|.
\NOTE It is NOT \LISPI (HIS NAME IS (DOUG LENAT))|.\eton
\NOTE These ``*\underspace\underspace''
variables can only be used in lists --- 
an error might be generated when such variables are embedding
in arbitrary S-expressions.\eton
\HINT If you are clever, you could use the \LISPI (PGM)| you wrote last assignment
for coding this function. 
Notice also how must easier this function,
(\LISPI (PGM)|,) would have been to write with this \LISPI CODE|ing facility.
\tnih
\Hint You will need the LISP primitive function, \LISPI EXPLODE|, which takes
an atom and returns a list of its letters. 
E.G. \LISPE \funct EXPLODE[ FRED ] \eq '(F R E D)|.
\tnih

\HeadC ⊂Part 2⊃
Write a function \LISPE \funct MTCH?[ pat, sexp ]|, which returns \T
if there is some assignment to the 
``?\underspace\underspace''
and
``*\underspace\underspace'' variables of the pattern,
\LISPI pat| which would cause \LISPE \funct Code[ pat ]| to return \LISPE sexp|.
As a side effect, \LISPE MTCH?| will perform these bindings.
So, \LISPE \funct MTCH?[ (A ?Z ?Z), (A (Q . E) (Q . E)) ]| would return \T,
and also set \LISPI ?Z| to 
\LISPI (Q . E)|.
Note this pattern \LISPI (A ?Z ?Z)| will match precisely
lists of three elements whose
first element is the atom \LISPI A|, and whose second and third elements are equal.
\LISPE \funct MTCH?[ (A *Z D), (A (F) (Q . E) D) ]|
also returns \T, and performs
\LISPI (setq *Z ((F) (Q . E)) )|.

\HeadC ⊂Part 3⊃
Now write a function \LISPE \funct MATCHES[ pat, sexp ]|,
which searches for an instance of the pattern \LISPI pat| within the
\LISPI sexp|.
It should return \NIL if no such pattern can be found, or else
the \LISPI CONS|ed pair, (\cons ⊂T . instance⊃), where
\LISPI instance|, is the (first) S-expression within \LISPI sexp| which matched 
\LISPI pat|.
As before, the appropriate variables should be bound.
\QUEST 3\ (Optional).
Rewrite the above functions to return meaningful error statements if
this function call, in this environment, would return some LISP error.
\HINT You may need the function 
\LISPI \funct Boundp[ x ]|, which returns \T if 
the atom \LISPI x| is bound, and \NIL otherwise.\tnih
\QUEST 4\ (Self-Generation).
Write a non-trivial (in particular, non-atomic)
expression that evaluates to itself.
That is, if you type in this expression, the result of LISP's evaluatation
will be this same literal expression.
You may use only pure LISP --- i.e. no global variables, \LISPI SETQ|s,
\LISPI DEFUN|s, \LISPI EVAL|s, etc.
\LISPI LAMBDA| expressions are permitted, and standard pure LISP functions,
such as 
\LISPI LIST| and \LISPI QUOTE|, may be used.

\QUEST 5\ (New LISP Cells).
This is an extension to the function \LISPE ME|, defined in class, which
returns an S-expression
EQUAL [but not EQ] to its sole argument, after
generating new internal LISP-cells.
Let \LISPE \funct New-Guts[ list, $n$ ]| return an equal list
whose top $n$ levels have been replaced.
That is, \LISPI \funct MAPCAR[ EQ, list, {\funct New-Guts[ list, 1 ]} ]|
should return a list of \T{}s, although 
\LISPI (eq list, {\funct New-Guts[ list, 1 ]})| is \NIL.
If the second argument is the atom ``\LISPI INFINITY|'', then all internal
cells should be replaced.
\QUEST 6\ (Auxilary Functions).
There are several functions which have been mentioned often  in class,
but never defined. Until now.
You are to write the following functions:
\NOTE In all, \LISPI f| is a function, \LISPI u| is a list
and \LISPI v| is a standard element of this \LISPI u|.
\LISPI v$↓∞$| is the last element of \LISPI u|.\eton
{\ninepoint
$$\vcenter{\halign{\lft{\LISPI \funct #[ f, u ]|}⊗\lft{\rm #}\cr
MAPAPPEND⊗Appends together the results of \LISPI \funct f[ v ]|, in order.\cr
EVERY⊗Returns \NIL iff \LISPI \funct f[ v ]| is ever \NIL, else
\LISPI \funct f[ v$↓∞$ ]|.\cr
ANY⊗Returns first non-\NIL \LISPI \funct f[ v ]|, else \NIL.\cr
NONE⊗Returns \T iff \LISPI \funct f[ v ]| is always \NIL, else \NIL.\cr
NOT-ALL⊗Returns \T iff any \LISPI \funct f[ v ]| is \NIL.\cr
COUNT⊗Returns the number of 
\LISPI v $\in$ u| for which \LISPI \funct f[ v ]| is non-\NIL.\cr
}}$$}

\QUEST 7\ (Ordering).
\HeadC ⊂Part 1⊃
Write a function \LISPI \funct SORT[ u ]| which returns its argument,
the list of real numbers \LISPI u|, in ascending order.
That is, if \LISPI v \assign \funct SORT[ u ]|, then 
\LISPI $∀$w $\in$ v. [w $\in$ u]| and 
\LISPI $∀$w$↓1$,w$↓2$. [w$↓2 \in$ \funct MEMBER[ w$↓1$, v ] $\→$ w$↓2 ≥$w$↓1$]|.
(Recall 
\LISPI MEMBER[ w$↓1$, v ]| is the list of members of \LISPI v| which follow
the element \LISPI w$↓1$| if 
\LISPI w$↓1$ $\in$ v|, or \NIL otherwise.

\HeadC ⊂Part 2⊃
Why might it be advantageous to represent sets as ORDERED lists 
(again of unique elements,) rather than the unordered types used in class?
\HINT Efficient sorting can be done in $O( n \log n )$ time.\tnih

\HeadC ⊂Part 3⊃
Rewrite the functions \LISPI MakeSet|
and \LISPI IsSet|
to deal with this convention.
(You may assume the binary predicate \LISPI GT| will act 
like Greater-Than for all LISP atoms.)
\par\vfill\eject
\end